home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 August: Tool Chest / Dev.CD Aug 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / OS / FWMemory / Sources / FWObjecH.cpp < prev    next >
Encoding:
Text File  |  1994-04-21  |  17.2 KB  |  530 lines  |  [TEXT/MPS ]
  1. //========================================================================================
  2. //
  3. //    File:                FWObjecH.cpp
  4. //    Release Version:    $ 1.0d1 $
  5. //
  6. //    Creation Date:        3/28/94
  7. //
  8. //    Copyright:    © 1993, 1994 by Apple Computer, Inc., all rights reserved.
  9. //
  10. //========================================================================================
  11.  
  12. #ifndef FWPLATME_H
  13. #include <FWPlatMe.h>
  14. #endif
  15.  
  16. #ifndef FWOBJECH_H
  17. #include <FWObjecH.h>
  18. #endif
  19.  
  20.  
  21. //========================================================================================
  22. // CLASS FW_CPrivChunkyBlock
  23. //========================================================================================
  24.  
  25. //----------------------------------------------------------------------------------------
  26. // FW_CPrivChunkyBlock::FW_CPrivChunkyBlock
  27. //----------------------------------------------------------------------------------------
  28.  
  29. FW_CPrivChunkyBlock::FW_CPrivChunkyBlock()
  30. {
  31.     SetBlockType(kBlockTypeId);
  32.     SetMagicNumber(kMagicNumber);
  33.     fNext = NULL;
  34. }
  35.  
  36. //----------------------------------------------------------------------------------------
  37. // FW_CPrivChunkyBlock::FW_CPrivChunkyBlock
  38. //----------------------------------------------------------------------------------------
  39.  
  40. FW_CPrivChunkyBlock::FW_CPrivChunkyBlock(unsigned int sizeIndex,
  41.                                  unsigned int blockIndex)
  42. {
  43.     SetSizeIndex(sizeIndex);
  44.     SetBlockIndex(blockIndex);
  45.     SetBlockType(kBlockTypeId);
  46.     SetMagicNumber(kMagicNumber);
  47.     fNext = NULL;
  48. }
  49.  
  50. //----------------------------------------------------------------------------------------
  51. // FW_CPrivChunkyBlock::GetChunk
  52. //----------------------------------------------------------------------------------------
  53.  
  54. FW_CChunk* FW_CPrivChunkyBlock::GetChunk(FW_BlockSize blkSize)
  55. {
  56.     FW_CChunk *chk 
  57.         = (FW_CChunk *) ((FW_BytePtr) this - sizeof(FW_SPrivChunkHeader) - blkSize * GetBlockIndex());
  58.     return chk;
  59. }
  60.  
  61. //----------------------------------------------------------------------------------------
  62. // FW_CPrivChunkyBlock::IsBusy
  63. //----------------------------------------------------------------------------------------
  64.  
  65. Boolean FW_CPrivChunkyBlock::IsBusy(FW_BlockSize blockSize)
  66. {
  67.     return this->GetChunk(blockSize)->IsBlockBusy(GetBlockIndex());
  68. }
  69.  
  70. //----------------------------------------------------------------------------------------
  71. // FW_CPrivChunkyBlock::SetBusy
  72. //----------------------------------------------------------------------------------------
  73.  
  74. void FW_CPrivChunkyBlock::SetBusy(FW_BlockSize blockSize, Boolean busy)
  75. {
  76.     this->GetChunk(blockSize)->SetBlockBusy(GetBlockIndex(), busy);
  77. }
  78.  
  79.  
  80. //========================================================================================
  81. // FW_CChunk
  82. //========================================================================================
  83.  
  84. //----------------------------------------------------------------------------------------
  85. // FW_CChunk::FW_CChunk
  86. //----------------------------------------------------------------------------------------
  87. #pragma segment HeapSeg
  88.  
  89. FW_CChunk::FW_CChunk(short blocksPerChunk,
  90.                      unsigned int sizeIndex,
  91.                      FW_BlockSize blockSize)
  92. {
  93.     fHeader.fBlockBusyBits = 0;
  94.     void* blkPtr = (void *) ((FW_BytePtr) this + sizeof(FW_SPrivChunkHeader));
  95.     for (unsigned int i = 0; i < blocksPerChunk; i++)
  96.     {
  97.         FW_CPrivChunkyBlock *blk = new(blkPtr)FW_CPrivChunkyBlock(sizeIndex, i);
  98.         blkPtr = (void *) ((FW_BytePtr) blkPtr + blockSize);
  99.     }
  100. }
  101.  
  102. //----------------------------------------------------------------------------------------
  103. // FW_CChunk::IsBlockBusy
  104. //----------------------------------------------------------------------------------------
  105. #pragma segment HeapSeg
  106.  
  107. Boolean FW_CChunk::IsBlockBusy(unsigned int whichBlock)
  108. {
  109.     unsigned short mask = 0x0001;
  110.  
  111.     for (short i = 0; i < whichBlock; i++)
  112.         mask = mask << 1;
  113.  
  114.     return (fHeader.fBlockBusyBits & mask) != 0;
  115. }
  116.  
  117. //----------------------------------------------------------------------------------------
  118. // FW_CChunk::SetBlockBusy
  119. //----------------------------------------------------------------------------------------
  120.  
  121. void FW_CChunk::SetBlockBusy(unsigned int whichBlock, Boolean busy)
  122. {
  123.     unsigned short mask = 0x0001;
  124.  
  125.     for (short i = 0; i < whichBlock; i++)
  126.         mask = mask << 1;
  127.  
  128.     if (busy)
  129.         fHeader.fBlockBusyBits |= mask;
  130.     else
  131.         fHeader.fBlockBusyBits &= ~mask;
  132. }
  133.  
  134. //----------------------------------------------------------------------------------------
  135. // FW_CChunk::GetBlock
  136. //----------------------------------------------------------------------------------------
  137.  
  138. FW_CPrivChunkyBlock* FW_CChunk::GetBlock(unsigned int blkIndex, FW_BlockSize blkSize)
  139. {
  140.     FW_CPrivChunkyBlock * blk 
  141.         = (FW_CPrivChunkyBlock *) ((FW_BytePtr) this + sizeof(FW_SPrivChunkHeader) + blkIndex * blkSize);
  142.     return blk;
  143. }
  144.  
  145.  
  146. //========================================================================================
  147. // FW_CObjectHeap
  148. //========================================================================================
  149.  
  150. //----------------------------------------------------------------------------------------
  151. // FW_CObjectHeap::FW_CObjectHeap
  152. //----------------------------------------------------------------------------------------
  153. #pragma segment HeapSeg
  154.  
  155. FW_CObjectHeap::FW_CObjectHeap(unsigned long initialSize,
  156.                    unsigned long incrementSize,
  157.                    short blocksPerChunk) :
  158.     FW_CBestFitHeap(initialSize, incrementSize),
  159.     fBlockSizes(ObjectHeap_kDefaultBlockSizes)
  160. {
  161. #ifdef FW_DEBUG
  162.     CompilerCheck();
  163. #endif
  164.  
  165.     fBlocksPerChunk = blocksPerChunk;
  166.  
  167.     for (fNumberOfBlockSizes = 0; fBlockSizes[fNumberOfBlockSizes]; fNumberOfBlockSizes++)
  168.         ;
  169. }
  170.  
  171. //----------------------------------------------------------------------------------------
  172. // FW_CObjectHeap::FW_CObjectHeap
  173. //----------------------------------------------------------------------------------------
  174. #pragma segment HeapSeg
  175.  
  176. FW_CObjectHeap::FW_CObjectHeap(const FW_BlockSize* blockSizes,
  177.                    unsigned long initialSize,
  178.                    unsigned long incrementSize,
  179.                    short blocksPerChunk) :
  180.     FW_CBestFitHeap(initialSize, incrementSize),
  181.     fBlockSizes(blockSizes)
  182. {
  183. #ifdef FW_DEBUG
  184.     CompilerCheck();
  185. #endif
  186.  
  187.     fBlocksPerChunk = blocksPerChunk;
  188.  
  189.     for (fNumberOfBlockSizes = 0; fBlockSizes[fNumberOfBlockSizes]; fNumberOfBlockSizes++)
  190.         ;
  191. }
  192.  
  193. //----------------------------------------------------------------------------------------
  194. // FW_CObjectHeap::IObjectHeap
  195. //----------------------------------------------------------------------------------------
  196. #pragma segment HeapSeg
  197.  
  198. void FW_CObjectHeap::IObjectHeap()
  199. {
  200.     this->IBestFitHeap();
  201. }
  202.  
  203. //----------------------------------------------------------------------------------------
  204. // FW_CObjectHeap::~FW_CObjectHeap
  205. //----------------------------------------------------------------------------------------
  206. #pragma segment HeapSeg
  207.  
  208. FW_CObjectHeap::~FW_CObjectHeap()
  209. {
  210. }
  211.  
  212. //----------------------------------------------------------------------------------------
  213. // FW_CObjectHeap::DoAllocate
  214. //----------------------------------------------------------------------------------------
  215. #pragma segment HeapSeg
  216.  
  217. void* FW_CObjectHeap::DoAllocate(FW_BlockSize size, FW_BlockSize& allocatedSize)
  218. {
  219.     if (size + FW_CPrivChunkyBlock::kBusyOverhead > fBlockSizes[fNumberOfBlockSizes - 1])
  220.         return FW_CBestFitHeap::DoAllocate(size, allocatedSize);
  221.     else
  222.     {
  223.         unsigned int sizeIndex = this->SizeIndex(size);
  224.         allocatedSize = fBlockSizes[sizeIndex] - FW_CPrivChunkyBlock::kBusyOverhead;
  225.         return this->AllocateBlock(sizeIndex);
  226.     }
  227. }
  228.  
  229. //----------------------------------------------------------------------------------------
  230. // FW_CObjectHeap::DoBlockSize
  231. //----------------------------------------------------------------------------------------
  232. #pragma segment HeapSeg
  233.  
  234. FW_BlockSize FW_CObjectHeap::DoBlockSize(const void* ptr) const
  235. {
  236.     FW_CPrivChunkyBlock *block
  237.         = (FW_CPrivChunkyBlock *) ((FW_BytePtr) ptr - FW_CPrivChunkyBlock::kBusyOverhead);
  238.         
  239.     if (block->GetBlockType() == FW_CPrivBestFitBlock::kBlockTypeId)
  240.         return FW_CBestFitHeap::DoBlockSize(ptr);
  241.     else
  242.         return fBlockSizes[block->GetSizeIndex()] - FW_CPrivChunkyBlock::kBusyOverhead;
  243. }
  244.  
  245. //----------------------------------------------------------------------------------------
  246. // FW_CObjectHeap::DoFree
  247. //----------------------------------------------------------------------------------------
  248. #pragma segment HeapSeg
  249.  
  250. void FW_CObjectHeap::DoFree(void* ptr)
  251. {
  252.     FW_CPrivChunkyBlock *block 
  253.         = (FW_CPrivChunkyBlock *) ((FW_BytePtr) ptr - FW_CPrivChunkyBlock::kBusyOverhead);
  254.         
  255.     if (block->GetBlockType() == FW_CPrivBestFitBlock::kBlockTypeId)
  256.         FW_CBestFitHeap::DoFree(ptr);
  257.     else
  258.         this->FreeBlock(block);
  259. }
  260.  
  261. #ifdef FW_DEBUG
  262. //----------------------------------------------------------------------------------------
  263. // FW_CObjectHeap::DoIsValidBlock
  264. //----------------------------------------------------------------------------------------
  265. #pragma segment HeapSeg
  266.  
  267. Boolean FW_CObjectHeap::DoIsValidBlock(void* ptr) const
  268. {
  269.     Boolean isBlockValid = false;
  270.     
  271.     FW_CPrivChunkyBlock *block
  272.         = (FW_CPrivChunkyBlock *) ((FW_BytePtr) ptr - FW_CPrivChunkyBlock::kBusyOverhead);
  273.  
  274.     if (block->GetBlockType() == FW_CPrivBestFitBlock::kBlockTypeId)
  275.         isBlockValid = FW_CBestFitHeap::DoIsValidBlock(ptr);
  276.     else
  277.         isBlockValid
  278.             = block->GetSizeIndex() <= fNumberOfBlockSizes &&
  279.               block->GetBlockIndex() <= fBlocksPerChunk &&
  280.               block->GetMagicNumber() == (unsigned int) FW_CPrivChunkyBlock::kMagicNumber;
  281.  
  282.     return isBlockValid;
  283. }
  284. #endif
  285.  
  286. //----------------------------------------------------------------------------------------
  287. // FW_CObjectHeap::DoReset
  288. //----------------------------------------------------------------------------------------
  289. #pragma segment HeapSeg
  290.  
  291. void FW_CObjectHeap::DoReset()
  292. {
  293.     FW_CPrivChunkyBlockStack clr;
  294.  
  295.     for (int i = 0; i < fNumberOfBlockSizes; i++)
  296.         fFreeLists[i] = clr;
  297.  
  298.     FW_CBestFitHeap::DoReset();
  299. }
  300.  
  301. //----------------------------------------------------------------------------------------
  302. // FW_CObjectHeap::AllocateBlock
  303. //----------------------------------------------------------------------------------------
  304. #pragma segment HeapSeg
  305.  
  306. void *FW_CObjectHeap::AllocateBlock(unsigned int sizeIndex)
  307. {
  308.     if (fFreeLists[sizeIndex].Top() == NULL)
  309.         this->CreateNewChunk(sizeIndex);
  310.  
  311.     FW_CPrivChunkyBlock * blk = fFreeLists[sizeIndex].Pop();
  312.     if (blk != NULL)
  313.     {
  314.         blk->SetBusy(fBlockSizes[sizeIndex], true);
  315.         return (void *) ((FW_BytePtr) blk + FW_CPrivChunkyBlock::kBusyOverhead);
  316.     }
  317.     else
  318.         return NULL;
  319. }
  320.  
  321. //----------------------------------------------------------------------------------------
  322. // FW_CObjectHeap::CreateNewChunk
  323. //----------------------------------------------------------------------------------------
  324. #pragma segment HeapSeg
  325.  
  326. void FW_CObjectHeap::CreateNewChunk(unsigned int sizeIndex)
  327. {
  328.     FW_BlockSize allocatedSize;
  329.     FW_BlockSize allocSize = sizeof(FW_SPrivChunkHeader) + fBlocksPerChunk * fBlockSizes[sizeIndex];
  330.     FW_CChunk * chk = new(FW_CBestFitHeap::DoAllocate(allocSize, allocatedSize))FW_CChunk(fBlocksPerChunk, sizeIndex, fBlockSizes[sizeIndex]);
  331.     if (chk != NULL)
  332.     {
  333.         for (unsigned int i = 0; i < fBlocksPerChunk; i++)
  334.         {
  335.             FW_CPrivChunkyBlock * blk = chk->GetBlock(i, fBlockSizes[sizeIndex]);
  336.             blk->SetBusy(fBlockSizes[sizeIndex], false);
  337.             fFreeLists[sizeIndex].Push(blk);
  338.         }
  339.     }
  340. }
  341.  
  342. //----------------------------------------------------------------------------------------
  343. // FW_CObjectHeap::FreeBlock
  344. //----------------------------------------------------------------------------------------
  345. #pragma segment HeapSeg
  346.  
  347. void FW_CObjectHeap::FreeBlock(FW_CPrivChunkyBlock* blk)
  348. {
  349.     blk->SetBusy(fBlockSizes[blk->GetSizeIndex()], false);
  350.     fFreeLists[blk->GetSizeIndex()].Push(blk);
  351.  
  352.     // Check to see if all blocks in this block's FW_CChunk are free, if so then free the
  353.     // FW_CChunk.
  354.  
  355.     FW_CChunk *chk = blk->GetChunk(fBlockSizes[blk->GetSizeIndex()]);
  356.     if (!chk->IsBusy())
  357.     {
  358.         // Remove blocks in this FW_CChunk from the free list. This is the achililles hill
  359.         // of the Heap. Its difficult to remove blocks from a singly linked list
  360.         // rapidly.
  361.  
  362.         void *begAddr = chk;
  363.         void *endAddr = (void *) ((FW_BytePtr) chk + 
  364.                                     sizeof(FW_SPrivChunkHeader) +
  365.                                     fBlocksPerChunk * fBlockSizes[chk->GetSizeIndex()]);
  366.         fFreeLists[chk->GetSizeIndex()].RemoveRange(begAddr, endAddr);
  367.         FW_CBestFitHeap::DoFree(chk);
  368.     }
  369. }
  370.  
  371. //----------------------------------------------------------------------------------------
  372. // FW_CObjectHeap::SizeIndex
  373. //----------------------------------------------------------------------------------------
  374. #pragma segment HeapSeg
  375.  
  376. unsigned int FW_CObjectHeap::SizeIndex(FW_BlockSize size)
  377. {
  378.     for (unsigned int i = 0; i < fNumberOfBlockSizes; i++)
  379.         if (size + FW_CPrivChunkyBlock::kBusyOverhead <= fBlockSizes[i])
  380.             return i;
  381.  
  382.     // Uh oh! An internal error:
  383.     
  384.     PLATFORM_DEBUGGER_STRING("Internal error in FW_CObjectHeap::SizeIndex");
  385.     
  386.     return 0xFFFFFFFF;    // the former way of handling the internal error
  387.                         // we leave it in to defeat an xlC warning
  388. }
  389.  
  390. #ifdef FW_DEBUG
  391. //----------------------------------------------------------------------------------------
  392. // FW_CObjectHeap::CompilerCheck
  393. //----------------------------------------------------------------------------------------
  394. #pragma segment HeapSeg
  395.  
  396. void FW_CObjectHeap::CompilerCheck()
  397. {
  398.     FW_CBestFitHeap::CompilerCheck();
  399.     
  400.     FW_CPrivChunkyBlock block;
  401.     
  402.     block.SetSizeIndex(0xF);
  403.     block.SetBlockIndex(0xE);
  404.     block.SetBlockType(FW_CPrivChunkyBlock::kBlockTypeId);
  405.     block.SetMagicNumber(0xC);
  406.     
  407.     PLATFORM_ASSERT(block.GetSizeIndex() == 0xF);
  408.     PLATFORM_ASSERT(block.GetBlockIndex() == 0xE);
  409.     PLATFORM_ASSERT(block.GetBlockType() == FW_CPrivChunkyBlock::kBlockTypeId);
  410.     PLATFORM_ASSERT(block.GetBlockType() != FW_CPrivBestFitBlock::kBlockTypeId);
  411.     PLATFORM_ASSERT(block.GetMagicNumber() == 0xC);
  412.     
  413.     block.SetSizeIndex(0x7);
  414.     block.SetBlockIndex(0x6);
  415.     block.SetBlockType(FW_CPrivBestFitBlock::kBlockTypeId);
  416.     block.SetMagicNumber(0x4);
  417.     
  418.     PLATFORM_ASSERT(block.GetSizeIndex() == 0x7);
  419.     PLATFORM_ASSERT(block.GetBlockIndex() == 0x6);
  420.     PLATFORM_ASSERT(block.GetBlockType() == FW_CPrivBestFitBlock::kBlockTypeId);
  421.     PLATFORM_ASSERT(block.GetBlockType() != FW_CPrivChunkyBlock::kBlockTypeId);
  422.     PLATFORM_ASSERT(block.GetMagicNumber() == 0x4);
  423. }
  424. #endif
  425.  
  426. //========================================================================================
  427. // FW_CPrivChunkyBlockStack
  428. //========================================================================================
  429.  
  430. //----------------------------------------------------------------------------------------
  431. // FW_CPrivChunkyBlockStack::FW_CPrivChunkyBlockStack
  432. //----------------------------------------------------------------------------------------
  433. #pragma segment HeapSeg
  434.  
  435. FW_CPrivChunkyBlockStack::FW_CPrivChunkyBlockStack()
  436. {
  437.     fHead.SetNext(NULL);
  438. }
  439.  
  440. //----------------------------------------------------------------------------------------
  441. // FW_CPrivChunkyBlockStack::FW_CPrivChunkyBlockStack
  442. //----------------------------------------------------------------------------------------
  443. #pragma segment HeapSeg
  444.  
  445. FW_CPrivChunkyBlockStack::FW_CPrivChunkyBlockStack(const FW_CPrivChunkyBlockStack& blk) :
  446.     fHead(blk.fHead)
  447. {
  448. }
  449.  
  450. //----------------------------------------------------------------------------------------
  451. // FW_CPrivChunkyBlockStack::operator=
  452. //----------------------------------------------------------------------------------------
  453. #pragma segment HeapSeg
  454.  
  455. FW_CPrivChunkyBlockStack& FW_CPrivChunkyBlockStack::operator=(const FW_CPrivChunkyBlockStack& blk)
  456. {
  457.     fHead = blk.fHead;
  458.     return *this;
  459. }
  460.  
  461. //----------------------------------------------------------------------------------------
  462. // FW_CPrivChunkyBlockStack::Pop
  463. //----------------------------------------------------------------------------------------
  464. #pragma segment HeapSeg
  465.  
  466. FW_CPrivChunkyBlock* FW_CPrivChunkyBlockStack::Pop()
  467. {
  468.     FW_CPrivChunkyBlock * blk = fHead.GetNext();
  469.     fHead.SetNext(blk->GetNext());
  470.     return blk;
  471. }
  472.  
  473. //----------------------------------------------------------------------------------------
  474. // FW_CPrivChunkyBlockStack::Push
  475. //----------------------------------------------------------------------------------------
  476. #pragma segment HeapSeg
  477.  
  478. void FW_CPrivChunkyBlockStack::Push(FW_CPrivChunkyBlock* blk)
  479. {
  480.     blk->SetNext(fHead.GetNext());
  481.     fHead.SetNext(blk);
  482. }
  483.  
  484. //----------------------------------------------------------------------------------------
  485. // FW_CPrivChunkyBlockStack::RemoveRange
  486. //----------------------------------------------------------------------------------------
  487. #pragma segment HeapSeg
  488.  
  489. void FW_CPrivChunkyBlockStack::RemoveRange(void *begAddr, void *endAddr)
  490. {
  491.     FW_CPrivChunkyBlock *prevBlk = &fHead;
  492.     FW_CPrivChunkyBlock *curBlk = fHead.GetNext();
  493.  
  494.     while (curBlk != NULL)
  495.     {
  496.         void *curAddr = curBlk;
  497.  
  498.         if (curAddr >= begAddr && curAddr <= endAddr)
  499.         {
  500.             prevBlk->SetNext(curBlk->GetNext());
  501.             curBlk = curBlk->GetNext();
  502.         }
  503.         else
  504.         {
  505.             prevBlk = curBlk;
  506.             curBlk = curBlk->GetNext();
  507.         }
  508.     }
  509. }
  510.  
  511. //----------------------------------------------------------------------------------------
  512. // FW_CPrivChunkyBlockStack::Top
  513. //----------------------------------------------------------------------------------------
  514. #pragma segment HeapSeg
  515.  
  516. FW_CPrivChunkyBlock* FW_CPrivChunkyBlockStack::Top()
  517. {
  518.     return fHead.GetNext();
  519. }
  520.  
  521. //----------------------------------------------------------------------------------------
  522. // FW_CPrivChunkyBlockStack::~FW_CPrivChunkyBlockStack
  523. //----------------------------------------------------------------------------------------
  524. #pragma segment HeapSeg
  525.  
  526. FW_CPrivChunkyBlockStack::~FW_CPrivChunkyBlockStack()
  527. {
  528. }
  529.  
  530.